package 分割等和子集;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/7 10:19
 * @description:
 */
public class Solution {
    public boolean canPartition(int[] nums) {
        // 这道题用回溯算法会超时，继续研究发现可以使用 dynamic programming
        // ① dp数组及其含义：dp[i]表示背包容量为i时，装下数字的最大值
        // ② 状态转移公式：dp[i] = Math.max(dp[i], dp[i-nums[i]] + nums[i]);
        // ③ 初始化dp数组：如果nums有负数，那么就需要初始化非0下标为负无穷，如果全为正数，初始化为0即可
        // ④ 遍历顺序：先遍历物品（nums），再遍历背包（nums）
        // ⑤ 举例推导dp数组：输入 1，5，11，5时
        //                 dp数组： 0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 10, 11 ==> dp[11] == 11

        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1 || nums.length == 1) {
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
//                System.out.println(Arrays.toString(dp));
            }
        }

        return dp[target] * 2 == sum;
    }
}